//
// Created by Administrator on 2021/5/20.
//

//给一非空的单词列表，返回前 k 个出现次数最多的单词。
//返回的答案应该按单词出现频率由高到低排序。如果不同的单词有相同出现频率，按字母顺序排序。

#include <string>
#include <iostream>
#include <vector>
#include <unordered_map>
#include <queue>
#include <algorithm>

using namespace std;

class Solution { // 优先队列
public:

    vector<string> topKFrequent(vector<string> &words, int k) {
        unordered_map<string, int> fre;
        for (auto &x:words) ++fre[x];
        auto cmp = [](pair<string, int> &m, pair<string, int> &n) {
            return m.second == n.second ? m.first < n.first : m.second > n.second;
        };
        priority_queue<pair<string, int>, vector<pair<string, int>>, decltype(cmp)> pq(cmp); // 小堆顶
        for (auto &x:fre) {
            pq.push(x);
            if (pq.size() > k) pq.pop();
        }
        vector<string> ans(k);
        for (int i = k - 1; i >= 0; --i) {
            ans[i] = pq.top().first;
            pq.pop();
        }
        return ans;
    }
};

class Solution2 { // 排序
public:
    vector<string> topKFrequent(vector<string> &words, int k) {
        unordered_map<string, int> cnt;
        for (auto &word : words) {
            ++cnt[word];
        }
        vector<string> rec;
        rec.reserve(cnt.size());
        for (auto&[key, value] : cnt) {
            rec.emplace_back(key);
        }
        sort(rec.begin(), rec.end(), [&](const string &a, const string &b) -> bool {
            return cnt[a] == cnt[b] ? a < b : cnt[a] > cnt[b];
        });
        rec.erase(rec.begin() + k, rec.end());
        return rec;
    }
};

int main() {
    vector<string> v{"i", "love", "leetcode", "i", "love", "coding"};
    Solution2 sol;
    auto ans = sol.topKFrequent(v, 2);
    for (auto &x:ans) cout << x << endl;
    return 0;
}